perm filename CACHE.424[AM,DBL] blob
sn#436949 filedate 1979-04-24 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00022 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 \input paper.tex
C00006 00003 \NSECP{INTRODUCTION}
C00022 00004 \NSECP{THE ASSUMPTIONS}
C00025 00005 \SSEC{A Model of Intelligence}
C00033 00006 \SSEC{A Model of Intelligent Program Organization}
C00043 00007 \SSEC{A Model of (Present) Computers}
C00046 00008 \NSECP{SELF-MODIFICATION & -MONITORING:}
C00047 00009 \SSEC{DYNAMICALLY MODIFYING ITSELF}
C00058 00010 \SSSEC{EXTENDING A SCHEMATIZED REPRESENTATION}
C00072 00011 \SSEC{DYNAMICALLY MONITORING THE TASK ENVIRONMENT}
C00087 00012 \NSECP{CACHING: INTELLIGENT REDUNDANCY}
C00090 00013 \SSEC{Types of Caches}
C00094 00014 \SSEC{An Example}
C00103 00015 \SSEC{Contrasts with Psychological Ideas of Economy}
C00108 00016 \SSEC{Storing and Updating Cached Values}
C00122 00017 \SSEC{The Spectrum of Data Reductions}
C00126 00018 \NSECP{EXPECTATION-SIMPLIFIED PROCESSING:}
C00138 00019 \NSECP{LEVELS OF ABSTRACTION:}
C00160 00020 \NSECP{COGNITIVE ECONOMY REVISITED}
C00167 00021 \NNSECP{Bibliography}
C00177 00022 \NNSECP{Acknowledgements}
C00178 ENDMK
C⊗;
\input paper.tex
\TITL{COGNITIVE ECONOMY}
\vskip 20pt
\ctrline{\:=in Artificial Intelligence Systems}
\vfill
\AUTHO{Douglas B. Lenat, \ Stanford University}
\AUTHO{Frederick Hayes-Roth, \ Rand Corporation}
\AUTHO{Philip Klahr, \ Rand Corporation}
\vfill
\vskip 10pt plus 2pt
\NNSECP{ABSTRACT}
Intelligent systems can explore only tiny subsets of their potential
external and conceptual worlds. To increase their effective
capacities, they must develop efficient forms of representation,
access, and operation.
In this paper we develop
several techniques which do not sacrifice expressibility, yet enable
programs to (semi-)automatically improve themselves and thus increase
their productivity.
The basic source of power is the ability to predict the way that the program will
be used in the future, and to tailor the program to expedite such uses.
Abstraction, caching, and
expectation-simplified processing are principal examples of such
techniques.
We discuss the use of these and other economic principles for modern AI systems. Our
analysis leads to some counterintuitive ideas and proposed
policies which are not generally followed because their contribution
to overall cognitive utility is not readily apparent. For example,
we challenge the typical practice of storing properties ``economically"
in hierarchical inheritance nets. That non-redundant storage practice
provides some storage cost savings, but significantly increases
processing costs. As an alternative, we suggest storage schemes
to improve performance by exploiting various forms of redundancy
consistent with general caching heuristics.
\vfill
\eject
\NSECP{INTRODUCTION}
When we build an AI program, we often find ourselves caught in the following
tradeoff: On the one hand, we want to develop our initial systems quickly
and painlessly, since they are experimental and ephemeral. On the other hand,
we want our systems to run as efficiently as possible, to mi\-ni\-mize the
temporal delays and to reduce the cpu time and space re\-quired.
We are torn between
{\it expressi\-bility} and {\it effi\-ciency}.
Many AI researchers {\sl cum} language designers have focused on {\it
expressibility}, the problem of rapidly constructing a working
experimental vehicle.\foo{This objective is apparent in the goals of
{\:c SAFE} [Balzer et al. 77],
{\:c PSI} [Green 77],
{\:c EMYCIN} [Feigenbaum 77],
{\:c RITA} [Anderson and Gillogly 76],
{\:c ROSIE} [Waterman et al. 79],
and
{\:c KRL} [Bobrow and Winograd 77].}
They have produced some superlative software such as
Interlisp's {\:c DWIM}, File, and Break packages.\foo{[Bobrow and Raphael 74] is
still an excellent discussion of the issues involved in such ``AI language"
efforts.}
Four fundamental techniques
utilized in highly {\it expressive} programs are:
({\it i}) reliance upon a very-high-level language,
({\it ii}) planning and reasoning at multiple levels of abstraction,
({\it iii}) inference by pattern-directed knowledge sources, and
({\it iv}) mi\-ni\-mal, nonredundant representation, as in a canonical
gene\-rali\-zation/spe\-ciali\-za\-tion hierarchy.
This paper addresses the second goal of AI programming,
{\it efficiency}.
We present techniques which do not sacrifice expressibility, yet enable
programs to (semi-)automatically improve themselves and thus increase
their productivity.
The basic source of power is the ability to predict the way that the program will
be used in the future, and to tailor the program to expedite such uses.\foo{This
approach is sometimes used {\it manually}, as when a program is quickly coded
in an expressive but inefficient form, used heavily, and then recoded in a
much more optimized form. Thus, e.g., Ray Carhart spent 1977
rewriting DENDRAL (streamlining its CONGEN module) for a minicomputer.}
The traditional approach to program optimization has assumed that the
programmer characterizes the predicted program behavior (e.g., by explicitly
providing assertions) or that static analysis can identify significant
optimization opportunities. Three types of methods for analyzing program
descriptions in this way include:
({\it i}) analyzing
program flow and structure [Knuth 1968] [Dijkstra 76],
({\it ii}) designing data structures to be appropriate,
and ({\it iii}) compiling (as in the {\:c FORTRAN H} compiler) and optimizing
transformations of the program (as in
[Darlington and Burstall 73 77] or [Balzer et al. 77].)
We advocate the use of methods more {\it dynamic} than these. Rather than
improving the static description of a program, we propose
to modify the program structure to adapt it to its
operational environment.\foo{Some
earlier automatic programming systems [Darlington and Burstall 73]
[Lenat 75] [Low 74] [Kant 77] [Barstow 77]
were designed to improve programs' efficiency, and many of their
ideas have found their way into the techniques we now describe.
Those systems
had program construction, transformation, and optimization as their primary
task; we are proposing general methods to provide
self-improving abilities
to other kinds of AI programs
(understanders, theory formers, expert simulators, planners, etc.).}
One valuable source of prediction comes from the program's experiences as it runs.
If a program can ``learn" from its experiences, it might try applying each piece of
newly acquired knowledge to the task of specializing itself, modifying itself
to run more efficiently in the current runtime environment.
We believe that a program's ``intelligence" can be increased in this way;
that is, by increasing its ability to
acquire appropriate knowledge, to organize that knowledge, and to refine
the conditions under which that knowledge is recognized to be applicable.
For any fixed quanta of manpower ({\it sic}) resources we expend, there is a
limit to the size/complexity of programs which can be successfully implemented.
This barrier might be overcome by programs which are self-extending, which actively
do things to enlarge their input domain, their capabilities.
Three ``dynamic'' abilities which make a program {\it efficient} are:
\noindent $\bullet $
{\bf Dynamic self-monitoring} (the ability to sense, record, and analyze
dynamic usage) {\bf and self-modification} (the ability to use that
knowledge to redesignrecompile itself with more appropriate
representations, algorithms, data structures; i.e., {\sl intelligent learning}.)
\noindent $\bullet $
{\bf Caching of computed results}
(storing the results of frequently-requested
searches, so they needn't be repeated over and over again; i.e.,
{\sl intelligent redundancy}.)
\noindent $\bullet $
{\bf Expectation-filtering}
(using predictions to filter away expected, unsurprising data,
thereby freeing up processing time for more productive subtasks;
i.e., {\sl intelligent focus of attention}.)
A fourth ability, which we shall also discuss in this paper, is one of the
more static techniques mentioned earlier, a kind of ``designing appropriate
data structures":
\noindent $\bullet $
{\bf Multiple levels of abstraction}
(redundant representation of knowledge at several levels of abstraction
can be an economical way of structuring a knowledge base, especially if the
program's tasks are large and the resources available for different tasks
vary widely in magnitude;
i.e., this is a technique for {\sl intelligent knowledge organization}.)
\yskip
``{\it Cognitive economy}'' is the term by which we describe such heightened
productivity.
Computer programs, no less than biological creatures, must perform
in an environment: an externally imposed set of demands, pressures,
opportunities, regularities.\foo{For a developed treatment of the
import of the ``task
environment'', see [Newell & Simon 72].}
Extending this analogy, we find that
{\sl cognitive economy is the degree to which a program is adapted to its
environment}, the extent to which
its internal capabilities (structures and processes) accurately
and efficiently reflect
its environmental niche.
\hbox par 2.9in{ % this makes a space for the little figure; see below.
Notice that representing a corpus of knowledge as a mi\-ni\-mal
(canonical) gen\-erali\-za\-tion/spe\-ciali\-za\-tion hierarchy, with
interpretatively-com\-puted in\-he\-ri\-tance, is {\it not} cognitively economical:
this technique
fa\-vors ex\-pres\-si\-bi\-lity, compaction of re\-pre\-sentation, at the expense of
performance. It is true that a dog is a mammal, and a mammal is an
animal, and from those two we could compute that a dog is an animal (see
Fig. 1), but it is more cognitively economical to store one redundant arc
than to recompute it frequently. Psychological studies
[Hayes-Roth and Hayes-Roth 74] [Rips et al. 75] indicate
just such redundancies being created and strengthened by repetitions.
}
% [[in space above, insert DIAGRAM OF DOG/MAMMAL/ANIMAL,
% WITH REDUNDANT ARC AS A !STRONG! DOTTED ARROW]]
Obviously, the economy of specific representations and related inference
methods depends heavily on underlying machine architectures and costs. We
assume that intelligent systems aim chiefly to produce useful results
(e.g., novel hypotheses) as rapidly as possible. In short, they should
search cleverly and fast. Thus, {\sl a priori} notions of aesthetics or design
economy have little bearing on cognitive economy. Massive redundancies
in storage, processors, and inference processes seem more directly
relevant. Furthermore, we suppose that, like people, intelligent software
should eliminate slow, interpretive searches for previously solved
problems (especially if the same problems are repeated often).
To this end, cognitive economy may be achieved
through dynamic compilation of action sequences. Such compiling would
reduce the time-cost to effect the corresponding behavior; on the other
hand, this efficiency would be gained at the cost of interpretability,
interruptibility, and modifiability. These are desirable attributes where
a program potentially needs continual changing.
In typical situations, both efficiency
of compiled forms and accessibility to declarative forms are intermittently
needed. These different needs point again to the economic benefits of
maintaining simultaneously alternative and redundant representations.
Every scientific theory is constructed in a rich context of surrounding
theories, methods, and standards determining which experiments are
reasonable ones to perform and which point of view to take when interpreting
the results --- in short, a {\it paradigm}. We feel it useful
to articulate the ``core" of our paradigm (the assumptions our theory
rests upon) before delving into more detail about cognitive economy.
For that reason, the next section is devoted to a presentation of our
assumptions, including:
a model for intelligence
(Section 2.1), a model for how intelligent computer programs may be
organized (Section 2.2), and a model of the characteristics of present
computing engines (Section 2.3).
Later sections assume these models, and contain detailed discussions and
examples of the main components of cognitive economy:
dynamic self-monitoring and self-modification (Section 3),
caching of computed results (Section 4),
and expectation-filtering (Section 5).
One interesting result that emerges in Section 6
is the prediction that as task size
grows large enough, the same techniques that currently support expressiveness
(e.g., multiple levels of abstraction) will become important for efficiency
--- for cognitive economy --- as well.
\NSECP{THE ASSUMPTIONS}
{\bf Summary:\ \sl The claims we make presuppose that ``intelligence" can be
adequately modelled as heuristic search, guided by
pattern-directed rules, implementable on a uniprocessor.}
\yskip
\noindent Our theories are erected upon a foundation of assumptions, including:
(i) We continually face searches in more or less immense spaces;
intelligence is the ability to bring {\it appropriate} knowledge to bear,
to speed up such searching. Increasing intelligence then comprises
increasing knowledge, improving its organization, and refining the
conditions for its
applicability. How are these new discoveries made? Empirical induction
(generalizing from experimental and other observations), analogy, and the
criticism of existing theory all lead to new conjectures, new
possibilities.
(ii) Intelligent systems can make the applicability of their knowledge
explicit by representing that knowledge as condition-action rules ({\:cIF {\sl
situation} THEN {\sl appropriate reaction}}). Such pattern-directed
inference systems (PDIS) can benefit from a schema representation (frame,
unit, being, script, etc.), because this adds structure which the rule
descriptions can exploit.
(iii) Current computing technology presents us with limited cycles, cheap storage,
and expensive knowledge acquisition.
While the reader can turn immediately to a discussion of our
detailed ideas on cognitive economy (beginning in
Section 3), it may be useful to examine the
above assumptions in more detail first.
\SSEC{A Model of Intelligence}
{\bf Summary:\ \sl Since ``intelligence" depends upon bringing relevant
knowledge to bear, it can be increased not only by adding new knowledge,
but also by better organizing the existing knowledge.}
\yskip
Many human cognitive activities, including most of those commonly referred
to as ``requiring intelligence," can be cast as searches, as explorations
through a search space, meandering toward some goal. We call a
problem-solver ``more intelligent'' if it can work efficiently toward a
solution even in the face of an immense search space and an ill-defined
goal. Somehow, it is imposing more structure on the problem, and using
that to search more effectively. How might it do this?
According to our model of human intelligence, it accomplishes the task by
bringing knowledge to bear, knowledge not supplied explicitly in the
problem statement. This knowledge can be about problem-solving in general
(e.g., how to recognize and break cultural blocks [Adams 74])
or about the problem
domain specifically (e.g., which groups of chemical
atoms can usually be treated as aggregate
superatoms [Feigenbaum 77]).
This implies that a problem solver can become more effective by (i)
increasing its knowledge, (ii) better organizing its knowledge, and (iii)
refining its criteria for deciding when various pieces of knowledge are
applicable. In terms of production (If-Then) rules, these correspond to
adding new rules, modifying the data structure in which rules are held,
and modifying the conditions (If parts) of existing rules.
One very basic assumption we are making is that of {\it continuity}:
the problem-solving environment does not change its character too
radically, too rapidly.
If the program abstracts from its experiences a plausible heuristic H, it may be
able to analyze past scenarios to verify that possessing and obeying H
would definitely have improved its performance (e.g., led to the current
state of knowledge quicker);
but its only justification for believing that H will help it in the {\it
future} is the empirical evidence for the continuity of the environment.
Learning can be translated effectively into action only when the structure of
the environment has not altered too greatly.
A related assumption is that of {\it irreversible knowledge accretion}.
Our body of facts and observations continually grows and only occasionally
shrinks. Certainly the abandonment of a whole system of thought is a
rare event indeed (ask Kuhn!),
whereas the adoption of new systems of thought is part of
the standard educational process.
\hbox par 2.9in{ % this makes a space for the little figure; see below.
New knowledge is discovered by
specializing some broadly applicable but weak principles, or by
generalizing
particular experiences. The latter includes abstraction
(condense some experiences into
a heuristic which
would have greatly aided us in the past if only we'd had it) and
analogy (draw parallels not merely to other
existing facts and heuristics, but also to the {\sl paths} which led to
their discovery.)
One sometimes ``spirals in'' [Lakatos 76]
toward precision (see Fig. 2).}
%(hypothesize, criticise, and
%improve the hypothesis) [Lakatos 76].
\SSEC{A Model of Intelligent Program Organization}
{\bf Summary:\ \sl
Since we want our AI programs to access, reason about, and expand their own knowledge
bases, it is useful to represent such knowledge in a clean, modular form
(e.g., employing any one of the current schematized representations.)}
\yskip
The preceding remarks about intelligent problem solving apply equally to
``hardware" and ``wetware" alike. To be intelligent, computer programs
must ultimately grapple with the tasks of knowledge acquisition,
representation, and refinement. We cannot provide an absolute answer to how
they should be organized, but we can posit some design constraints which
have proven useful so far.
A very general heuristic in AI programming is the following: {\sl If your
program is going to modify its own {\bf X}, then make {\bf X} as
separable, clean, and explicit as possible.} In our case, {\bf X} can be
instantiated as ``knowledge," or as ``applicability conditions for each
piece of knowledge." In this case, the heuristic advises us to represent our
knowledge in a separate, clean, explicit form, say as knowledge modules
having some fixed internal
structure, and also advises us to keep the applicability
conditions for each knowledge module separate from the rest of the
knowledge it contains.
This naturally leads us to a pattern-directed inference system, in which
knowledge is broken into separate modules, each with an explicit set of
relevancy tests [Waterman and Hayes-Roth 78]. Such systems arising in
Pittsburgh may champion
syntactic purity, while those arising in
California may tend toward the baroque,
but such variations should not obscure their common source of
power. The PDIS architect breaks his program's knowledge into a set of
condition-action production rules.
Having a clean representation for rules means having a clean, precise,
elegant language in which to express them. By structuring the conceptual
knowledge of the system, by partitioning each module's knowledge into
several categories, a rule can condense an entire cumbersome description
into a simple reference (often a single pointer). The popular schematized
representations of
knowledge (scripts for episodes, frames for static situations, beings for
specialists, units for everything) enable a rule like ``If there are no
known methods specific to finding new examples of prime numbers, then..."
to have its condition coded as a simple null-test on the ``To-get" subslot of
the ``Examples" slot of the schema called `` Prime Numbers." By a judicious choice
of slot types and subslot types, the system builder can reduce most
triggering conditions to such quick checks on the state of various
(subslots of) slots of schemata.
Additional knowledge is required to locate efficiently all the rules which
{\it might} have their conditions satisfied in a given situation, and also
to decide which rules to execute (obey) among those whose IF parts
have triggered (been satisfied).
\SSEC{A Model of (Present) Computers}
{\bf Summary:\ \sl
Since we are considering the problem of building computer models of
intelligent behavior, many of our assumptions deal with the
characteristics of present-day computers. They are the symbol manipulators
we use, but were not designed for that general purpose.}
\yskip
The foremost quality of computing machines, as we know them today, is their
limited ``inferential bandwidth." Although they provide virtually {\sl (sic)}
limitless storage capacity, these machines can process only a small fraction
of this information in a reasonable amount of time. Two primary reasons
for this disparity between storage and generation capacities include:
(1) knowledge acquisition proceeds slowly and expensively; and (2) inference
processes depend on operations that ordinarily require cycles of
uniprocessor systems.
The first problem places a {\it cultural} limitation on the
development of intelligent machines. This development is restrained by our
inability to express what we would like our machines to do or to convert
these expressions into effective machine interpretable codes.
The second
problem reflects a {\it technological} constriction of our potential. The
so-called von Neumann bottleneck, caused by machine architectures that
sequentially interpret program steps through a single logical processor,
strongly motivates concern for programs that can mini\-mize unnecessary
computations.
In some future environment, perhaps neither of these problems
will persist. In the meantime, however, we assume that two of the best ways
to increase AI system productivity, derived from these current limitations,
will be to expedite knowledge acquisition and to avoid unnecessary computing
(for instance, by opting to ``store" rather than ``compute").
\NSECP{SELF-MODIFICATION & -MONITORING:}
{\:=\ctrline{INTELLIGENT LEARNING}}
\yyskip
We would like an intelligent system to be able to improve its
performance dynamically. To accomplish this, a program
must first be able to monitor its processing, i.e.,
to sense, record, and analyze
its representations, data structures, algorithms, inference procedures, and the
way they are currently being relied upon.
It can then use this gathered knowledge to modify or redesign itself to
perform more efficiently.
\SSEC{DYNAMICALLY MODIFYING ITSELF}
{\bf Summary:\ \sl
We illlustrate various ways in which a program might use to
advantage knowledge gleaned dynamically: selecting (or perhaps even {\it
discovering}) new data structures, representations, algorithms, etc. which
seem better suited to the current runtime environment, the current user,
the current problem, etc.}
\yskip
In order for a program to dynamically modify its own
processing, it must examine, integrate and apply knowledge of
the task domain, knowledge about programming in general, knowledge about the
actual runtime environment, and knowledge gathered from observing its own
processing behavior. The next section sketches ways in which dynamic program
performance could be self-monitored. This section draws attention to the
possibility of applying such usage data to modifying --- or in the extreme
re-synthesizing --- the program.
Tasks can be specified anywhere from a pure ``What'' (desired
input/output behavior) to a pure ``How'' (precise algorithms, data structures,
representations, formats). It has been observed [Feigenbaum 77] that one
of the goals of AI research is to push our ability from the How end toward
the What end of that spectrum. This often takes the form of designing a new
higher-level language than any that hitherto existed, one which takes over
more of the program implementation. We can see this as far back as
assemblers replacing machine language, and as recently as KRL [Bobrow and
Winograd 77] and the Molgen Units Package [Stefik 78] extending
Interlisp.
Assuming, then, that the user
desires merely to specify What, an intelligent language (automatic code
synthesizer) must decide How. Upon what can it base its design?
Previous efforts have employed knowledge about program transformations
[Burstall and Darlington 77] [Balzer et al. 77], programming techniques and
task-specific knowledge [Green and Barstow 78], and
--- if the input language is at all complex --- information to enable
the succesful translation of the input specification into a sufficiently
precise specification of What [Lenat 75].
A couple recent efforts have begun to guide the decision-making during code
synthesis by algorithmic analysis [Kant 77] or even by aesthetics
[Lenat 76]. But all these methods are
{\it static}: they feed off a fixed base of initially-supplied knowledge,
heuristics, constraints, suggestions, facts. The user supplies a
specification for the desired program, and the knowledge base is employed
to produce that target.
What might it mean for a program to modify itself dynamically?
Suppose a hospital
simulation program were specified, and on the basis of
the user speci\-fi\-ca\-tion an event-driven system\foo{Two
entries know which happened before the other, but
not absolute times of day at which they occurred.} appeared to be
the best design. During
subsequent usage, it's observed that the majority of
questions refer to
precise times of event occurrences. If this had been part of the initial
specification, the design decision would have been made differently, say in
favor of a synchronous time-step simulation. It would be no less useful a
change in the system even at this late date. Even if this redesign is
performed, the environment might keep
changing in various ways, slowly, perhaps even cyclically.
Future redesigns might be mandatory {\sl ad infinitum}.
The attractiveness of having a system which can automatically adapt
itself to its current runtime environment is apparent.
The simplest kind of adaptive abilities along this line would be to {\it select}
a data structure, a representation, or an algorithm from a set of well-known
choices
--- and to reserve the right and the ability to change that decision later.
One could gather knowledge about the relative strengths and weaknesses
of each choice [Kant 77]. This knowledge
could be in the form of rules which ask not only about static data, but which
sample the runtime environment of the program as well. For instance:
\noindent ``If
one conjunct appears to be false more often than any other, make it the first
one tested in the conjunction''
\noindent ``If each person will use the program only
once, briefly, it is not worth building a model of each such user''
\noindent ``A function that is used frequently and changed rarely should be
compiled.''
Such design questions could be answered initially, during program synthesis, but
our suggestion of automating the gathering of such data is a further step
toward the ``What" of artificial intelligence.
There is another possibility, much more exotic than the previous one,
which deserves attention: the discovery --- in ``real time" --- of new
types of data structures and representations which would be useful
for the program in its current environment.
Defining a new data structure is not as difficult as it may first appear:
a data structure can be thought of abstractly in terms of a set of operations
one wants to be able to perform on it (e.g., First, Last, Next, and Previous, for
lists). The set of desired operations need not be minimal nor concern itself
with which operations are most important, etc. The run-time usage of such
a data structure can be sampled, and that can guide the search for an
ever more appropriate implementation (e.g., in one usage, it might be
very useful for Last to be efficient, and Interlisp's {\:cTCONC}ing might be
chosen as an implementation; in another
environment, it might be useful for Next and Previous to be efficient, and
a doubly-linked implementation would be best).\foo{Dave Barstow is one of the few
AI researchers investigating issues such as these.}
The two points here are (i) the implementation of a data structure
may depend upon how it is commonly used in a particular spot in a program,
by a particular user, and (ii) a new kind of data structure may be defined
abstractly merely by selecting a set of operations; this choice, too, can
be made by examining the run-time data as it accumulates.
Defining a new {\it representation} is not quite so neat. In fact, humans have only
managed to find a handful of representations to date. In lieu of any constructive
suggestions along that line, we shall focus on {\it extending} a
given representation:
\SSSEC{EXTENDING A SCHEMATIZED REPRESENTATION}
{\bf Summary:\ \sl
The Eurisko program extends it schematized representation
by defining new types of
slots. It uses a very simple grammar for defining new slots from old ones (legal
moves), and a corpus of heuristic rules constrain that process (plausible moves).}
\yskip
For a schematized representation,\foo{Knowledge broken in pieces called
schemata, frames, concepts, units, scripts, which in turn are merely collections of
smaller pieces called properties, slots, facets, aspects.}
``extension" could
occur by defining
new types of slots. The Eurisko program (an extension of the AM
program [Lenat 76]) has this capability, and we shall
briefly describe how this mechanism was developed.
First, we isolated four ways in which new slots are defined from old
ones:
\yskip
\noindent {\bf STAR} (e.g., Ancestor $=↓{df}$ Parent$↑*$ which means a Parent of a
Parent of... of a Parent of me; the general case should be aparent);
\noindent {\bf UNION} (e.g., Parent $=↓{df}$ Father $\union$ Mother);
\noindent {\bf COMPOSITION}
(e.g., First-Cousin $=↓{df}$ Child$\circ$Sibling$\circ$Parent; i.e., any
child of any sibling of either of my parents);
\noindent {\bf DIFFERENCE}
(e.g., Remote-ancestor $=↓{df}$ Ancestor $-$ Parent).
\yskip
These four operators which define new types of slots
($\,↑*,\ \union,\ \circ,\ -$) are called {\it slot-combiners}.
\yskip
Next, we added to AM's knowledge base a concept for each type of slot, and
a concept for each type of slot-combiner. Figure 3 shows some of the
Generalizations and Star concepts. Note in particular the way in which
Generalizations is defined as Genl$↑*$ --- i.e., immediate generalizations,
{\it their} immediate generalizations, and so on.
\yyskip
\ctrline{\bf[FIGURE 3: 2 concepts]}
\yyskip
Finally, we modified the way in which slot entries are accessed.
To illustrate this, we choose a simple task in mathematics, whose paraphrase
is, ``What are all the generalizations of the concept `primes'?" The
traditional way in which {\:c (GET PRIMES GENERALIZATIONS)} would work is
to examine the property list of {\:c PRIMES}, looking for the attribute
{\:c GENERALIZATIONS}; if found, the entries listed there would be returned.
If, as in Fig. 4, there is no such attribute, the call upon {\:c GET} will
return {\:c NIL} (the empty list).
\yyskip
\ctrline{\bf[FIGURE 4: network of concepts from Primes up]}
\yyskip
What we modified was the
way in which any retrieval request of the form
{\:c (GET C F)}
operates. In case the
{\:c F}
attribute of
{\:c C}
has no entries (or doesn't exist), we examine the definition of
{\:c F}
and --- if one exists --- try to use it to compute the entries that could
legally be stored on the
{\:c F}
attribute of
{\:c C}. More precisely, before quitting
we try to
{\:c (GET F DEFN),}
and if that succeeds we apply it to
{\:c C.}
Let's continue the example of
{\:c (GET PRIMES GENERALIZATIONS).}
As we
see in Fig. 4 above, there are none recorded. So
{\:c GET}
now calls itself
recursively; our original call is replaced by
{\:c ((GET GENERALIZATIONS DEFN) PRIMES).}
But as Fig. 3 shows, there is no slot labelled
{\:c DEFN}
on the concept for
{\:c GENERALIZATIONS}.
So we recur one more time. By now our call has become
{\:c (((GET DEFN DEFN) GENERALIZATIONS) PRIMES).}
Here is part of the
{\:c DEFN}
concept:
\yyskip
\ctrline{\bf[FIGURE 5: DEFN concept]}
\yyskip
Luckily, it does have a
{\:c DEFN}
slot, so we end the recursion.
Applying the entry stored there to the argument ``{\:c GENERALIZATIONS},"
we see our original call becoming transformed into
{\:c [((GET (GET GENERALIZATIONS SLOT-COMBINER) DEFN)}
{\:c \hjust{\hskip 29pt (GET GENERALIZATIONS BUILT-FROM))}}
{\:c \hjust{\hskip 23pt PRIMES]}}
We see from Fig. 3 that
the slot-combiner of Generalizations is ``Star,"
and the argument
(old slot) which it is built from is ``Genl." So the entire call
shrinks into
{\:c (((GET STAR DEFN) GENL) PRIMES).}
The Star concept has an entry for its Defn slot;
it turns the preceding call into
{\:c (($\lambda$ (c) (CONS c (self (GET c GENL)))) PRIMES). }
This function first calls for
{\:c (GET PRIMES GENL),}
which is
{\:c NUMBERS,}
then calls
itself on
{\:c NUMBERS;}
that in turn calls for
{\:c (GET NUMBERS GENL),}
which is
{\:c OBJECTS,}
and calls itself recursively on
{\:c OBJECTS;}
that calls for
{\:c (GET OBJECTS GENL),}
which is
{\:c ANYTHING,}
and the next recursive call terminates
when it is discovered that
{\:c ANYTHING}
has no
{\:c GENL}
(no immediate generalization.)
The list
{\:c CONS}tructed and returned is thus
{\:c (PRIMES NUMBERS OBJECTS ANYTHING).}
These four items are the legal entries for the
{\:c GENERALIZATIONS}
slot of
{\:c PRIMES, }
according to the definition of
{\:c GENERALIZATIONS. }
Notationally there is no distinction between slots which are ``primitive"
(values actually stored as attributes on a property list) and slots which
are ``virtual" (values must be computed using the slot's definition).
A heuristic might refer to the Generalizations of Primes without knowing,
or caring, whether that initiated a single access or a dizzy chase.
To define a new kind of slot, then, one need merely specify one of the
slot-combiners and list the old pre-existing slots from which it is built.
Thus we might define a new slot, by creating a new concept (calling it,
say,
``{\:c DG}"), filling its
Slot-combiner slot with the entry ``Difference", filling its
``Built-from" slot with the arguments ``Generalizations Genl." This would
be a new kind of slot, one which returned all generalizations of a concept
except its immediate generalizations; the call
{\:c (GET PRIMES DG)}
would return
{\:c (PRIMES OBJECTS ANYTHING). }
It is only a small extension to see how new
kinds of slot-combiners can be defined. For instance, one which took
two old slotnames as arguments, f and g, and defined a new slot which was
f$↑*\circ\,$g$\,\circ\,$f$↑*$, would be extremely useful (e.g., in database
searches: see Fiksel and Bower [76]). In particular the crucial
slot ``Examples" is defined as Spec$↑*\circ\,$Immed-Exs$\,\circ\,$Spec$↑*$.
Here is another example of how the expanded
{\:c GET}
works:
we consider an access on the
{\:c PARENTS}
slot, when that slot is not primitive,
but rather is defined as the union of slots for father and mother.
{\:c (GET MERLE PARENTS)}
{\:c ((GET PARENTS DEFN) MERLE)}
{\:c (((GET DEFN DEFN) PARENTS) MERLE)}
{\:c (($\lambda$ (s) ((GET (GET s SLOT-DEFINER) DEFN) (GET s BUILT-FROM))) PARENTS) MERLE)}
{\:c (((GET (GET PARENTS SLOT-DEFINER) DEFN) (GET PARENTS BUILT-FROM)) MERLE)}
{\:c (((GET UNION DEFN) FATHER MOTHER) MERLE)}
{\:c ((($\lambda$ (s1 s2) ($\lambda$ (c) (LIST (GET c s1) (GET c s2)))) FATHER MOTHER) MERLE)}
{\:c (($\lambda$ (c) (LIST (GET c FATHER) (GET c MOTHER))) MERLE)}
{\:c (LIST (GET MERLE FATHER) (GET MERLE MOTHER))}
{\:c (LIST SID BETTY)}
{\:c (SID BETTY)}
\yskip
\noindent We have discussed
how a new slot {\it can} be defined; consider now how
a program is to know {\it when/how} to define a new one.
The new type of slot might be defined for purely
exploratory reasons (e.g., it's aesthetic to define ``first cousins'': the
specializations of the generalizations of a concept). The slot's definition
might be based soundly upon need --- or the absence of need. For example,
by monitoring usage, we might
notice that many concepts have a large number of entries for their {\:c F} slot,
and infer
that the {\:c F} slot should be specialized. This would lead us to create
several new slots, each having
fewer entries on the average than {\:c F} had, to cover the original {\:c F} slot.
E.g., if we noted that the Examples slot was heavily used,
we might consider creating new slots like Boundary-examples
and Typical-examples. The new kind of slot-combiner
defined in the previous paragraph
($\lambda\ (f,g)\ f↑*\circ\,g\,\circ\,f↑*$),
could be derived from the fact that those
slots which are most useful in the system (e.g., Isas, Examples) share that common
form; or it could be motivated purely from symmetry, and the existing good
uses of it would later be noticed in retrospect.
We close this section with a further exotic possiblity.
If the task domain of the system is the
exploration of (a domain isomorphic to) programming, some new
``theorem" might occasionally be discovered which can be incorporated into a
data structure or
algorithm (or even representation) to speed the whole system up or supplant it.
\SSEC{DYNAMICALLY MONITORING THE TASK ENVIRONMENT}
{\bf Summary:\ \sl
The previous section illustrated how a program might profit from knowledge
it gathered dynamically. This suggests that
rather than working on the given problem exclusively,
a program may be better off to expend some
time {\it learning} (about the specific problem, its broader domain, or
problem-solving in
general). Note this suggestion would encompass traditional education (being
told), empirical research (observing),
and theoretical exploration (predicting).
While such ``very high-level" problem-solving strategies typify human
problem-solvers (especially those of us who have
rationalized spending twenty or more years ``in school''), very few programs to date
have employed any of these forms of learning to improve their operation.}
\yskip
Some programs (and wish-lists for program capabilities) have included learning
more about the problem being worked on;\foo{ McCarthy's advice-taker and
Balzer's dialogue system (to get airline reservation programs written) would
be told, Gelernter's theorem-prover (employing diagrams as analogic
models) could observe, Lenat's AM
could observe and predict.}
in this paper, however, we are stressing learning about the
ways the program is being currently employed.
\SSSEC{Learning by Being Told}
There are many situations in which a user could provide advice to a program:
\yskip
{\it (a). } The user might want to convey to the program
some task-specific item: ``Integration by
parts won't work on this problem';' ``This is a very hard
problem.'' This can easily be input as part of the user's statement of the
problem for the system to work on; e.g., the user might designate some methods
as being preferred or constrained, he might estimate a resource allotment, etc.
{\it (b). } Another type of advice
will apply permanently to the nature of the program's functioning
(e.g., ``Answers, even if uncertain, must be produced in real time;''
``Hard problems will be
starred.'') Such knowledge can be reflected permanently in
the design of the program, in its code.
{\it (c). } But there is an intermediate level of advice, some information
the user knows will concern
the next several tasks to be submitted --- not just the present one and not
all future ones:
``The next four problems will be supplied in order of
expected difficulty;" ``Several of these problems share common assumptions
and raise related issues;" ``The user for the next entire
session will be a physician;" ``Until I find out why F34 returned NIL, I'll
be in debugging mode, not production mode." Such advice is rarely communicable
even to AI programs.
We believe this type of intermediate-level
advice would improve
programs if they had the opportunity to accept and use it.
In general, we would like to advise the program which capabilities to
consider and which to ignore during a prolonged period of solving closely
related problems.
A fixed (static) approach, for example, would be to define a few modes
(e.g., Debug, Demo, Production, Input,...) and permanently build into the code
all changes required to specialize the system for each mode. A flexible
(dynamic) approach would
provide a larger language in which the user could describe his current
mode of usage of the program (e.g., by typing ``{\:cUSAGE of KNOWLEDGE-BASE
will-be INCREASED VERY-MUCH}'').
The program would translate such statements into
changes in its data structures, algorithms, explanations, core management
strategies, etc. In the current example, heavy usage of the knowledge
base might
cause the program to swap out its compiler, optimizers, and other code,
enabling it to hold many more knowledge chunks at a time in core.
The ability to hold more knowledge in memory would directly affect the rate
and probability of productive inferences.\foo{Similar effects have been shown
for humans: [B. Hayes-Roth 1979 {\it Cognitive Science}, in press]}
\SSSEC{Learning by Observing}
Spending a little time/space reconfiguring to reflect the current state
of the world (the nature of the recent and succeeding inputs) seems
worthwhile; the problem is how to know what that abnormal nature of the
environment is. In the last subsection, we discussed the case where the
user explicitly tells the program. But this is often impossible (as when
the
user is unaware of an impending irregularity, or when the ``user'' is
Nature), and almost
always a nuisance (learning the language in which to express such advice,
remembering to do it, taking the time to do it).
The next step seems to be to allow the program to {\it infer} such facts
about its run-time environment from observations.
What kinds of self-monitoring can be usefully employed?
The method which comes to mind first, perhaps, is to save a complete
record of everything that ever happened to this program: all the inputs
it received (when, from whom), function calls and accesses it made internally,
paths it chose/rejected (and why),
and outputs it generated. The program could in principle
deduce, from such an exhaustive
history-list, patterns such as ``very light usage of
compiler;'' ``SQRT is always called
on the result of SUM-OF-SQUARES.''
The space costs of such an archive, and the temporal cost of the
procedures
to infer useful patterns, are surely prohibitive.
The more economical approach is to analyze in advance certain
features we would wish to look for in a complete history record, and then
to have the program record just enough dynamically to gather and maintain
those features. Some of these will be domain-independent and
commonly useful:
Frequency of calls on various functions, requests for subtasks, etc.;
Patterns in the arguments to calls on certain functions and inputs to the program;
Patterns in the sequence of calls on functions;
Patterns in functions' results (e.g., F34 always seems to
return a User-Name).
Some of the features will be domain-dependent specializations of the
preceding features (``Average degree of input equation'' is a special
``pattern in the input.'')
\SSSEC{Learning by Predicting}
The theoretician and the engineer share
a powerful technique: manipulating
a model of a system to generate predictions and identify those possible
outcomes that would be desirable.
This is a third route to learning.
How might programs produce it?
What sorts of theories, or models, can be employed to generate new
information?
{\it Models of the program's users} can be valuable. This includes
maintaining and extending profiles of individual users and whole
groups. When a user opens a dialogue with Eurisko with the word
``Let", it is a safe bet that he's a mathematician. Later, when he
uses the word ``function," his membership in that group makes it easy
to determine which meaning he has in mind
(instead of, say, what a physiologist or a computer scientist or sex therapist
might mean
by ``function.'')
When the program wishes to
mention $\sqrt{-1}$, it uses its
{\:c MATHEMATICIAN}
model to
choose an appropriate notation (``{\sl i}'' for mathematicians
instead of, say, ``{\sl j}'' for
engineers). Models can be arranged in a hierarchy, with inheritance
of features from more general groups to their subsets, a lattice
ultimately terminating in models of individuals. User inputs would
be recognized by various models, which would then hypothesize membership
in that group (or explicate some future conditions which would confirm or
deny such inclusion). Once triggered in this way, the user's apparent groups
(and its generalizations) would actively
filter his inputs and outputs, could modulate the program's actions (e.g., by
changing the worth of the ``Proof" concept, which in turn would change
the priority rating of tasks on an AM-like agenda and thus alter
the program's choice of what to work on next.)
New user models can be created either top-down (e.g., when a model has
many diverse instances or when it's proven historically to be very valuable,
then try to split
it into several specializations, each having a share of the general model's
instances) or bottom-up (i.e., notice that a group of individuals share a
set of common characteristics, and create a new user group out of them).
The preceding kind of prediction is based on a theory of user types, embodied
in a set of ``typical representative'' models. The same source of power can
be used in many ways: stereotyping of events (as in scripts), stereotyping
of static complexes (as in frames), stereotyping of communities (as in
actors, beings, and contract nets). In all these cases, the source of power
lies in quickly recognizing probable membership in (applicability of) some
schema, after which all the rest of the schema
(plus knowledge about all its generalizations) is presumed to be relevant.
Programs might build up and utilize scenarios of how problems are solved
typically in their domain. The building-up could be top-down via specialization
or bottom-up via generalization, or even ``sideways" via analogy. The
models would be used for prediction (recognize relevant models and activate
them, have them hypothesize probable future situations).
Together, the models would form a theory of how problems are
solved in that domain.
\NSECP{CACHING: INTELLIGENT REDUNDANCY}
{\bf Summary:\ \sl
``Caching'' the results of computations can dramatically improve the
performance of many programs. Reasoning can be brought to bear to decide
whether to cache, if so what to remember, and (later) whether or not to ignore
the cached value and recompute it. We often refer differently to ``caching''
depending upon what it is that's being retained:
open-ended, inductive searches can be condensed in hindsight (i.e. cached)
into heuristics, deductive searches can be cached into much less branchy
algorithms,
subroutines can be cached into tables of frequently called arguments and
resultant values, and variable quantities have their value cached simply by
the process of binding.}
\yskip
After computing some result, it is typically put to some use, and the result
itself is typically forgotten. If needed again, it is recomputed.
Hardware designers have long recognized (both theoretically and
empirically)
the tremendous gain in efficiency affordable by {\it caching}: recording
the result, at least temporarily, in case it is called for again soon.
If that occurs, then no time need be spent recomputing it.
Transferring that notion from hardware to software, and generalizing it
slighty, we have the philosophy we shall call {\it software caching}:
modifying memory to save computed results to speed subsequent accesses.
In this section, we discuss this principle, giving examples of its use
as well as identifying heuristics for determining when, why, and how to
cache.
\SSEC{Types of Caches}
The simplest case of caching occurs just after computing F(x), for some
function call F with argument x, by remembering the value returned.
Whenever F is called, we first check to see if a cached value is stored
(e.g., associative retrieval on function/argument/value triples; e.g.,
scanning a list of function/argument pairs for which values are
recorded, or hashing F and x, etc.) If no cached value is found,
F(x) is computed and cached for future usage.
If a cached value is found, then we must decide whether to accept it,
or else to ignore it, recompute it, and store the new value there.
In chess, this might correspond to storing the common openings --- a practice
which uses a great deal of storage, yet is cost-effective {\it because}
the book openings frequently recur.
But even this extravagant record-keeping is not complete: we have not saved
information about the {\it process} of computing F(x), the path that was
followed, the traps, the blind
alleys, the overall type of successful approach, etc.
While much more costly to record than simply the value returned by F,
this type of information can often be of extreme usefulness, especially
for the purposes of generalizing, of monitoring the runtime environment
of the program, of leading to new and better algorithms and data structures
(see Section 3).
The analogue in chess, e.g., was first hinted at by Newell, Shaw, and Simon
in their early chess paper [63], then elaborated by Berliner
in his thesis [74]: the idea that you should abstract out a
description of a path through the search tree, so
that the remainder of the search could partake of it.
If one path leads to a discovered check against you, so will many others.
You would be wiser to keep that threat in mind, instead of discarding all
your state information and blindly backtracking.
In other words, subtrees should communicate.
Similarly, in theorem proving, one could store (and perhaps even generalize)
partial proof trees --- and proof-finding experiences --- for use in subsequent
proof attempts. In {\:cSTRIPS} [Fikes et al. 72] we see a program caching
partial plans so it can later reuse them.
\SSEC{An Example}
To illustrate the process of caching values,
consider again the way in which
{\:c (GET PRIMES GENERALIZATIONS)}
was computed by
Eurisko, as explained in section 3.1.1. Several function calls were
required, and a fair amount of cpu time was expended. It would be quite
economical to store the value once computed, to save time in the future.
Eurisko simply stores
{\:c (PRIMES NUMBERS OBJECTS ANYTHING)}
as the value of the
{\:c GENERALIZATIONS}
attribute of
{\:c PRIMES.}
When the call on
{\:c GET}
is reissued, it
tries to access this very spot. Though it failed previously, it now would
succeed, and it would return the cached list almost instantly. No computing
would be done, the concepts of
{\:c STAR, DEFN, }
and
{\:c GENERALIZATIONS}
needn't be in
core now, and no space (even temporary space) would be required.
We saw earlier that notationally (e.g., to a rule) there was no need
to distinguish an access of a primitively-stored slot from an access of a
virtual, computed slot. Now we see that once the value is computed and
cached away, there may be no telling it from a primitive one.\foo{We might
prefer to enclose cached values within brackets, to indicate their nonprimitive
status.}
Thus, with but a small one-time cost, our program runs as quickly as if
all slots were primitive.
Note that in originally
computing Generalizations of Primes, it was necessary to call for
{\:c (GET GENERALIZATIONS DEFN),}
and the value of this virtual slot was also
computed. The Eurisko policy is to cache this value also. It is useful
because, when a request such as
{\:c (GET DUCK GENERALIZATIONS)}
is received, it
would otherwise have to be recomputed all over again. The definitions of
slots are very slowly --- if ever --- changing, hence the recomputation of
Defn of Generalizations is quite a rare event. Caching that value must be
cost-effective in the long run.
In general, we see that caching a value for slot F of concept C is
most applicable when the value can be expected to vary quite infrequently.
In Eurisko, this gives us the flexibility to redefine a slot's definition
if we wish, but (since this change of representation
will be rare) the program will run just about as
efficiently as if that capability
were absent. This is analogous to compiling: so long as the definition of
a function doesn't change too often, it's undisputedly worthwhile to compile
it. The caching of
{\:c DEFN}
and
{\:c GENERALIZATION}
slots is not in any way special;
the value of any virtual slot can be cached.
The careful reader may have spotted a difficulty in our caching policy:
what happens if the value {\it does} change? One way to check for this
would be to recompute the value, but of course if this is done too often
it negates the benefits of caching. Eurisko faces this problem by adding
some extra arguments to
{\:c GET,}
parameters which describe a
cost/benefit curve:
for each amount of resources expended and each
degree of precision of the result, this curve specifies precisely how
acceptable that resource consumption / accuracy of
solution pair is. One extreme of this is to provide
an ironclad limit on resources
and say ``Do the best you can
within these time/space/... limits." Another extreme
(most common in present-day programs) is to specify
an ironclad goal criterion (``Find an answer which is at
least {\sl this} good, no matter how long it takes to get.")
We are calling attention to the space in between
the two extremes.
To bring us back from the lofty heights of generality, let's see in more
detail how we got Eurisko to do this.
First, we linearized this space: we picked a
few significant parameters of it, and defined a description to be merely
a list of values for these parameters.
When a call on
{\:c GET}
was executed, and a cached value was encountered, a
formula relating these extra arguments to
{\:c GET}
would then determine whether
to accept that cache, or to ignore it and recompute the value.
Eurisko's parameters (extra arguments to
{\:c GET}) are:
cpu time to expend, space to expend, whether the user can be asked about
this, how fresh the cache must be, minimum amount of resources which must have
been expended at the time the cache was written.
So
{\:c (GET PRIMES GENERALIZATIONS 200 40 NIL 3 0)}
would allow any cached
value to be accepted if it appeared that recomputing would take more than
200 milliseconds, or would use up more than 40 list cells, or if the value
had been put there less than three Cycles ago.\foo{In Eurisko, a ``Cycle'' is the
time it takes to work on the top-rated task on the top-rated agenda.}
Otherwise, the cache would be ignored, a newer value would be computed, and
it would be stored away. With it would also be recorded the following information:
(i) the fact that it was
a cached value, not a primitive one, (ii) how long it took to compute,
(iii) how many list cells it used up in computing this value, (iv) the current
Cycle (number of tasks worked on so far). The above call on
{\:c GET}
might result
in the following value being stored on the
{\:c GENERALIZATIONS}
slot of
{\:c PRIMES:}
{\:c (*cache* \ (PRIMES NUMBERS OBJECTS ANYTHING) 54 6 9).}
\SSEC{Contrasts with Psychological Ideas of Economy}
When semantic networks first appeared in cognitive psychology, they
led to the idea that function should follow form. In particular,
since taxonomic knowledge structures were hierarchical, inference
processes would presumably follow the same inter-category network paths
each time the corresponding relation needed testing. It was for this
reason that Collins & Quillian [69][72] conjectured
that the time required to verify semantic relations would correlate with
distance in a corresponding ``economical" semantic network. Thus, they
showed that people ordinarily verified ``a canary is a bird" faster than
they could verify either of the two more remote relationships,
``a canary is an animal" or ``a canary has wings."
Subsequent research however showed that the needs of
particular retrieval experiences,
not {\sl a priori} categorizations, determined which inference paths humans would
follow and the associated response times.
A simple counterexample to the presumed hierarchical
retrieval schemes was found by Rips, Shoben and Smith [73]. They showed
that people access a familiar but so-called ``indirect"
relation such as ``a dog is an animal"
much faster than the supposedly immediate but less frequent
relation ``a dog is a mammal."
Using experimental materials and methods, Hayes-Roth & Hayes-Roth [75]
found that human memory seemed plastic and adaptive in many of the same ways
we have proposed for intelligent machine programs. Their results led them
to ``an adaptive model of memory, in which all learned relations are
represented directly, with strength proportional to experience. There is
also good evidence for redundancy in the network, with multiple routes
connecting nodes representing particular pairs of concepts" [75, p. 519].
In another study, Hayes-Roth and Hayes-Roth found evidence
that people understand and remember English texts directly in terms
of high-level lexical concepts, rather than low-level or primitive
concepts. They argued that cognitive processes would presumably
benefit if they could build directly upon the words or other meaningful
units of familiar language. Any system that needed to interpret and
store data in terms of primitive units, as is often assumed in
language understanding theories, would encounter many slower and costlier
searches. Both the empirical evidence and theoretical principles support
the idea that human language understanding exploits many kinds of caching.
In short, we have chosen the term caching to refer to these types of
redundant storage. Caching, to capture and exploit repetition and
regularity, will benefit both humans and machines of limited processing
capabilities.
\SSEC{Storing and Updating Cached Values}
The caching process involves storage and updating. For both of
these aspects, we can discuss details of when, why, how, and what.
The decisions that arise are made with the guidance of heuristic rules,
many of which are illustrated below in
Figs. 6 and 7.
We have omitted many of the
very general ``common-sense" heuristics, and those which deal with details
of Lisp programming. We also have specified the rules in English, rather than
in Lisp; we have freely used expressions like ``recently", although in any
encoding that would have to be made much more precise.
Finally, note that these heuristics are not {\it always} relevant; they are
applicable for many AI programs, running on
uniprocessing
PDP-10-sized computers, running
Interlisp, with a human user watching and interacting.
There would be other rules for other machine architectures and languages.
In other words, one could say that we have only partially specified the
IF-part (left hand sides) of the following heuristic rules. An alternative
would be to build up an entire knowledge base of heuristics just to determine
the applicability, the domains of relevance,
of the following (as a function of machine and language.)
\yyskip
\ctrline{\bf[[FIGURE 6: STORAGE PRINCIPLES]]}
\yyskip
\ctrline{\bf[[FIGURE 7: UPDATING PRINCIPLES]]}
\yyskip
\SSEC{The Spectrum of Data Reductions}
Caching, as we have described it, is merely the lowest-level of a tier of
data reduction processes, techniques for compiling hindsight into usable,
{\it more efficient}, more procedural forms.
To see this, consider the progression of ever more sophisticated tasks
which programs perform [see Fig. 8]: accessing a datum, calculating a
value from a fast algorithm, deducing a result by searching for a solution
or proof in a well-defined space,
inducing a result by a very open-ended search process.
Often there is the opportunity to take experiences at one of these levels of
sophistication and abstract them into an entity which is one level lower,
yet which appears to contain almost the same power.
Consider first the way in which we reduce induction. After
much experience with inducing, we produce a {\it heuristic rule} which
enables the same inferencing to be done in a much more controlled space,
in a much more deductive way. Heuristics reduce discovery tasks to mere
(!) symbolic manipulation within a well-defined system (as in AM [Lenat 76]).
Deduction is reduced similarly. By many painful deductions, we gain know\-ledge
of the space we are searching, e.g. by deriving many theorems about it.
Those theorems can then be used to vastly simplify our search. Ultimately,
the process becomes efficient calculation. A short, optimal algorithm may
be found, e.g., which replaces a search for a solution (this has recently
occurred with the ``{\sl n queens}'' chess problem.)
Now we see that our caching process is the next step in this progression.
It reduces a calculation (e.g., to traverse a particular access path to
gather all Ancestors of a node) by a lookup, by a single access of a datum
in memory.
\yyskip
\ctrline{\bf[[FIGURE 8: Progression of caching]]}
\yskip
%also variable binding fits in?
%ACCESS==> CALCULATE ==> DEDUCE ==> INDUCE BY OPEN=ENDED SEARCH
%
% \ / \ / \ /
%
% cache thm, alg heur rule
%
%[[note: saving multiple
%instantiations of the same rule at different levels of abstraction is
%NOT worth mentioning, I think, since it is a STATIC (eg planning) tactic;
%I may be wrong, and perhaps we should at least mention this v. briefly anyway]]
%
%[[Should we metnion explcitly the loss that may occur if the task involves
%a lot of reasoning one's
%way through delicate inference chains efficiently; or: a lot of
%synthetic reasoning or rule interaction?]]
%
\NSECP{EXPECTATION-SIMPLIFIED PROCESSING:}
{\:=\ctrline{INTELLIGENT FOCUS OF ATTENTION}}
\yyskip
{\bf Summary:\ \sl
For efficiency's sake, an intelligent system should be willing and
able to add new facts, but should be {\it eager} to add surprising new facts.
Surprises can only be noticed by contrast with {\it expectations}, so an intelligent
system should maintain a context of expectations and filter incoming observations
against that. Furthermore, expectations and surprises can aid an intelligent
system in comparing its model and processing of the domain to the real world.
Through such monitoring, discrepencies may be found and diagnosed, leading to
changes in the model making it more consistent with observed behavior. Our
discussion here centers on the importance of using such expectations
to focus and filter intelligent processing.}
\yskip
The world bombards our senses with data, much more than we can process
in detail in real time; yet we can't live in a hundred times real time.
We survive by ignoring most of that data, or, more precisely, by knowing
(almost immediately deciding)
what can be ignored. We maintain a set of expectations, against
which the incoming torrent is matched. Almost all of it will match those
expectations, and we then need merely process the unexpected inputs, the
surprising observations. We reserve our computing for those opportunities
which promise us genuine new facts, rather than reconfirmation of known ones.
Such concentration on the abnormal is a natural side-effect of being guided
by expectations --- albeit usually stereotyped ones --- about situations,
events, and people.
One is able to zip through most of what is encountered, match it immediately
to the active schema, and move on. The only processing which is slow and
tricky is that dealing with the remaining anomalies, exceptions, puzzles.
The more general position is that each slot indicates not merely a default,
but also an indication of how important it is to confirm that value.
Some slots will have meta-comments like ``I'm worth computing or
verifying'', or just the opposite. For example, in our ``Room''
frame, we have a
default Ceiling, but in everyday life
we know to not squander time checking that each room
we're in has a ceiling. Similarly for emergency exit signs:
they usually exist, and we rarely feel it's cost-effective to confirm that.
We have in
both sittuations a very fast algorithm we can apply if ever we are in a
situation in which we need that information. For ceilings, it's
$\lambda\ (\ )\ (look upwards)$; for exit
signs, it's ``look for red on white lettering.''\foo{
While this may seem to be a much more complex program to execute, recall that
if we truly need to run it --- say in a sudden power failure ---
we expect those lit signs to be one of the few things we could still see.}
The policy for whether, when, and how to check a default slot value can be
arbitrarily complex. The program may be designed to
reason at great length about how much time to expend re-confirming the expected.
It may reason about the task of reasoning about how much time to spend,
and so on.
\yskip
\noindent Several
increases in efficiency are realizable through expectation-filtering:
(a). Perceptual set: Expectations allow you to see what you expect with less effort
For emergency exit signs, when we need to find them, we know to look for horizontal
and vertical red lines; this is 99$\%$ effective. When we look at our red LED watch
and have a perceptual set to read the time, we of course would not mistake the
image for that of the EXIT.
(b). Surprise: If we observe Y when we expected X, our attention is captured.
In one way, sensitivity to data inconsistent with
expectations has been heightened. We saw in (a), above, that reliance on
frames will dull our chance of noticing a surprising datum
(since we will tend to interpret any data as consistent
with the current frame).
This point (b)
says that {\it if} we do notice it, then it will have a significant impact.
Carefully buiding up an expectation and then abrupting shattering it with a
jarring surprise is the archetypical template for a good joke.
As Arthur
Koestler observes, the jarring of conflicting matrices of thought is what
powers art ({\sl ah!}), science ({\sl aha!}) and humor ({\sl haha!}).
(c). Defer: By relying upon expectations, upon defaults, we can usually defer
processing to find the true value in the current case forever. At least, when
we {\it do} finally have to make a particular perception, it may at that time
be easier to make. When the ceiling is falling, it's easier to see; when all the
lights go out except for the EXIT signs, it's easier to see them.
Generalizing, we may state that it's worth a little computing to reason
out whether (and maybe even how long) a slot-filling
can be ignored.
(d). Predict and Prepare: This includes the whole continuum we discussed in
the Caching section: bind a variable, store the triple (F,x,F(x)), store enough
information so that F(x) could be recomputed very quickly, store information
which would make F'(x') more easily computable (for x' similar to x, and F'
similar to F), store away a partial model of the world with good and bad features
tagged. Notice that moving along this continuum, programs grow
more flexible, more descriptive (less scalar), more dynamic.
In all cases, the
motivation for doing this storage is to (i) speed up the recognition of
(the need to do) similar computations in the future, and (ii) speed up
or even eliminate those computations when you decide they {\it are} relevant
and you want the values they would return. These are the two uses of
scripts, but also of cached constants (e.g., caching the value returned
by OWNED-BY, a function from CARS to PEOPLE). A better example is {\it user models}:
they range from a single bit (E.g., a NOVICE/PRO toggle),
to a few numbers (e.g., in PARRY),
to a dynamic concept-modelling scheme (e.g., in Eurisko).
In the interests of cognitive economy, we conclude that programs should
build up expectations, monitor them,
and change their models as needed. A natural mechanism for doing this is
the use of pattern directed knowledge modules (PDMs), which can react to
changing situations, to sudden disconfirmations of predictions.
These can be used as triggers or demons; e.g., if
you hear someone shout ``Fire!" in a theater, that takes precedence over
Jane Fonda.
The second use of PDMs arises when an expectation is not met: the program then
also has some chance of modifying the culprit
rule(s) that made that false prediction (and/or
adding new rule(s) which would make the right one.)
%[[Mention TERIESIAS??]]
%
%[[ignore: This ties learning in very closely to scientific theory
% formation (at least the theories of knowledge which
% are activist, revolutionary conventionalist activist,
% methodological falsificationist, sophisticated.
% [those are the nodes descending in a genl/spec hier
% of theories of knowledge]
%
%]]
\NSECP{LEVELS OF ABSTRACTION:}
{\:=\ctrline{INTELLIGENT KNOWLEDGE STRUCTURING}}
\yyskip
{\bf Summary:\ \sl
An intelligent system's domain model is typically an approximation of reality.
It is often the case that knowledge exists at several levels of detail and
abstraction. The amount of detail required in intelligent processing depends
on the problem-solving context. By appropriately structuring knowledge, a
problem-solver can take advantage of abstraction by reasoning at the level
appropriate to the given situation. We argue here that abstraction
is crucial for intelligent systems which must process over large
knowledge bases or within widely-varying time constraints.}
\yskip
%[[mention McCarthy's common-sense reasoning example: a spilling coffee cup;
%we don't try to integrate the hydrodynamic differntial equations]]
In many real-life problem solving situations, the ``goal" is not a single,
precise answer. Rather, there is a cost-benefit tradeoff between the
accuracy of the solution and the amount of resources consumed in producing
it.
Computer programs which are designed only to return exact answers
lie at one extreme end of this curve, and rarely near the optimal point (of
diminishing returns).
This presupposes a kind of ``continuity'' in the
environment, as we discussed in Section 2.1. Namely, truncated search is
assumed to be better than random selection of a legal move.
Almost paradoxically, if the environment
is mercurial, then the optimal point on the tradeoff will cause our program to
be very {\it expressive}.
Let's look at an example of the omnipresent need to
approximate reality --- a need which is well met by maintaining multiple
representations of the world at various levels of abstraction;
i.e., an entry in the knowledge base has all its generalizations also
stored explicitly, redundantly.
A train accident occurs, and over two hundred people are injured. The
only large nearby hospital is called, and asked if they can handle the load.
The administrator queries his shiny new hospital operation simulator,
and it begins to chug
away. It looks over the state of each current patient, each physician,
each hospital resource. It begins simulating the arrival of the wounded, triage,
their movement and temporary storage in hallways, etc. After quite a while of
processing time,
it shows that the hospital will be saturated and unable to care for any more
incoming patients. The maximimum they can accept is 157 wounded passengers.
If ``quite a while" is several hours (which it very likely would be),
this type of anaysis is
simply inappropriate. There is a pressing need for a rough answer quickly;
a {\it human} hospital administrator would answer right away, or after a
very brief survey of a few parameters, and {\it so should
an intelligent program}.
In addition to aiding us in quickly approximating reality, multiple levels
of abstraction (``MLA") are useful for
{\it analogizing}: they can
make that process easier, faster, and occasionally even
more valid. Analogies can be recognized when two distinct concepts coincide
at some abstract level. Conversely, if (corresponding
slots of) two apparently related
concepts (such as two homonyms) do not share related structure at higher
levels of abstraction, that suggests that an analogy between them would be
superficial and lacking in power.
Multiple levels of abstraction cost a certain
amount to implement, both initially (man-hours of programming) and as the
program runs (cpu time spent maintaining the redundancy, choosing which level
to work on next, etc.) For problems of all sizes, this feature aids in the
expression of new problems to the program, since they may be input at whatever
level(s) seem appropriate to the user. Thus multiple levels of abstraction
will always add to expressiveness, and will either detract or add to
efficiency depending upon how small or large the task is.
MLA is very useful when the program's resources are
curtailed or, even better, varied dramatically in magnitude from run to run
(a program which was {\it always} limited to a 15-second execution time would
be designed specifically for that task, but a program which might get anywhere
from 5 seconds to 5 hours for the same simulation question could better
benefit from multiple levels of abstraction.)
MLA
contributes more to efficiency
as the quotient (task size)/(resource allotment) increases in size.
There is a more general result here: the methods which humans find useful for
easy expression of problems may be useful to programs attacking very large
problems. For instance, consider the decision about whether to do inference
by a system of pattern-invoked experts, or rather to preprocess the triggering
conditions into a big discrimination network. The former approach is more
expressive, the latter more efficient --- at least for small problems. For
very large tasks, the need to remain flexible grows very large. It is then
more economical to retain pattern-directed control (the compilation of the
patterns is so complex the whole procedure would have to be redone
frequently during the course of execution, if we opted for that alternative
instead.) A case in point is the HARPY speech understanding program
[Lowerre & Reddy 79]:
whenever the grammar changes --- at any level --- the entire speech recognition
network must be recompiled. HEARSAY II [Lesser and Erman 77],
while slower in performance, has
sufficient flexibility (from several independent pattern-directed knowledge
sources) to obviate such monolithic integrative recompilation delays.
\NSECP{COGNITIVE ECONOMY REVISITED}
{\bf Summary:\ \sl We identified three dynamic characteristics and one
static characteristic that serve the needs of intelligent adaptation.
First, we showed that most inferential systems can benefit
from
{\it learning}
about their task environment and their own behavior. For example,
they can exploit new schemata or different slot-names to simplify and
restructure their knowledge. Second, the need to explore large
search spaces with some repetitive regularity motivates the use of
{\it caching}
to save partial results. We described a variety of techniques to
implement caching, and explained how caching specific results is
one of a spectrum of methods that can make trade-offs among precision,
speed, certainty, and generality. The third dynamic capability
we identified was
{\it expectation-filtering.}
In general, intelligent systems need to exploit their knowledge about
typicality to reduce their cognitive load and increase their attention
to important data. In many situations, we believe that expectations
can both reduce processing requirements for handling ordinary events
as well as simplify the identification of surprising events. Finally,
we argued that
{\it multiple levels of abstraction} (MLA)
provide economical representations for complex tasks. In many simple
environments, the advantages of MLA are minimal
and may not even justify their costs. Thus, routine tasks may
warrant the kind of knowledge compilation that would convert an initial,
expressive MLA knowledge-base into a fast, integrated, and largely
uninterpretible code. Conversely, as task complexity and variability
increase, MLA increasingly provides a basis for intelligent and rapid
restructuring.}
\yyskip
In the years to come, AI programs will employ greatly expanded
knowledge bases and, as a consequence, they will explore increasingly
open-ended problem spaces. Already, a few existing systems show signs
of having more potentially interesting things to do than they have
resources to pursue (e.g., AM, Eurisko). In the past decades of
intelligent systems R&D, several design concepts have emerged in
response to contemporary needs for creating ever larger knowledge
bases. For example, many researchers proposed multiple levels of
abstraction and automatic property inheritance as keystones of
efficiency or ``cognitive economy." We believe that the value of such
mechanisms derives largely from their usefulness in describing initial
knowledge bases. Once an intelligent system begins to explore the
consequences of its knowledge and to solve novel problems in a
dynamic environment, it needs to adapt its knowledge to achieve
faster and more profitable retrievals.
A theory of cognitive economy
should explain why knowledge needs to be adapted and should prescribe
how to do it. In this paper, we have tried to lay the groundwork for such a
theory. To date, cognitive science has developed few systems and
generated few analytical arguments on which to base such a theory.
In contrast, we have approached this problem by defining the issues,
illustrating situations that motivate various types of economies, and
proposing design and re-design heuristics that support intelligent
adaptations. These heuristics embody the gross features of an eventual
theory and suggest numerous paths for future research.
In conclusion, we have tried to show what cognitive economy
{\it is}
and
{\it is not.}
It does
{\it not}
consist of a set of static knowledge-base design principles, such
as those proposing taxonomic concept structures with automatic
property inheritance. Rather, cognitive economy is a feature of
those intelligent systems that learn to solve problems efficiently
and consequently realize more of their lifetime potential. Toward
that end, we have proposed an initial set of four basic design
characteristics. We anticipate these characteristics will find
widespread application in many future AI systems. As knowledge
bases expand and basic software obstacles are overcome, AI systems
will increasingly address the same question facing intelligent
humans: ``What would I most like to accomplish next, and how can I do that
economically?"
\NNSECP{Bibliography}
Adams, J. L.
Conceptual Blockbusting.
W.H. Freeman: San Francisco, 1974.
Anderson, R. H. and Gillogly, J. J. Rand intelligent terminal agent
(RITA): design philosophy. R-1809-ARPA, The Rand Corporation,
Santa Monica, Calif., 1976.
Balzer, R., Goldman, N., and Wile, D. Informality in program
specifications.
Proc. of the 5th Int. Joint Conf. on Artificial Intelligence,
Cambridge, Mass., 1977, 389-397.
Barstow, D. A knowledge-based system for automatic program
construction.
Proc. of the 5th Int. Joint Conf. on Artificial Intelligence,
Cambridge, Mass., 1977, 382-388.
Berliner, H. J. Chess as problem solving: the developments of a tactics
analyzer, Ph.D. Dissertation, Carnegie-Mellon University, Pittsburgh, 1974.
Bobrow, D. G. and Raphael, B. New programming languages for
artificial intelligence research.
Computing Surveys, 6,
1974, 153-174.
Bobrow, D. G. and Winograd, T. An overview of KRL, a knowledge
representation language.
Cognitive Science, 1,
1977, 3-46.
Burstall, R. M. and Darlington, J. A transformation system for
developing recursive programs.
Journal of the ACM, 24,
1977, 44-67.
Collins, A. M. and Quillian, M. R. Retrieval time from semantic memory
Journal of Verbal Learning and Verbal Behavior, 8,
1969, 240-247.
Collins, A. M. and Quillian, M. R. How to make a language user. In
E. Tulving and D. Donaldson (eds.),
Organization of Memory.
Academic Press: New York, 1972.
Conrad, C. Cognitive economy in semantic memory.
Journal of Experimental Psychology, 92,
1972, 149-154.
Darlington, J. and Burstall, R. M. A system which automatically improves
programs.
Proc. of the 3th Int. Joint Conf. on Artificial Intelligence,
Stanford, Calif., 1973, 479-485.
Dijkstra, E. W.
A Discipline of Programming,
Prentice-Hall: Englewood Clifs, N.J., 1976.
Feigenbaum, E. A. The art of artificial intelligence: themes and
case studies of knowledge engineering.
Proc. of the 5th Int. Joint Conf. on Artificial Intelligence,
Cambridge, Mass., 1977, 1014-1029.
Fikes, R. E., Hart, P. E., and Nilsson, N. J. Learning and executing
generalized robot plans.
Artificial Intelligence, 3,
1972, 251-288.
Fiksel, J. R. and Bower, G. H. Question answering by a semantic
network of parallel automata.
Journal Math. Psych., 13,
1976, 1-45.
Gelernter, H. Realization of a geometry-theorem proving machine. In
E. A. Feigenbaum and J. Feldman (eds.),
Computers and Thought,
McGraw-Hill: New York, 1963, 134-152.
Green, C. A summary of the PSI program synthesis system.
Proc. of the 5th Int. Joint Conf. on Artificial Intelligence,
Cambridge, Mass., 1977, 380-381.
Green, C. and Barstow, D. On program synthesis knowledge.
Artificial Intelligence, 10,
1978, 241-279.
Hayes-Roth, B. and Hayes-Roth, F. Plasticity in memorial networks.
Journal of Verbal Learning and Verbal Behavior, 14,
1975, 506-522.
Hayes-Roth, B. and Hayes-Roth, F. The prominence of lexical information
in memory representations of meaning. Journal of Verbal Learning
and Verbal Behavior, 16, 1977, 119-136.
Hayes-Roth, B. and Walker, C. Configural effects in human memory.
Cog\-ni\-tive Sci\-ence,
in press, 1979.
Hayes-Roth, F., Klahr, P., Burge, J., and Mostow, D. J. Machine
methods for acquiring, learning, and applying knowledge. P-6241,
The Rand Corporation, Santa Monica, Calif., 1978.
Hayes-Roth, F. and Lesser, V. R. Focus of attention in the Hearsay-II
speech understanding system.
Proc. of the 5th Int. Joint Conf. on Artificial Intelligence,
Cambridge, Mass., 1977, 27-35.
Kant, E. The selection of efficient implementations for a high level
language.
Proc. ACM SIGART-SIGPLAN Symp. on Artificial Intelligence and Programming
Languages,
SIGART Newsletter 64, 1977, 140-146.
Klahr, P. Planning techniques for rule selection in deductive
ques\-tion-ans\-wer\-ing. In D. A. Waterman and F. Hayes-Roth (eds.),
Pattern-Directed Inference Systems.
Academic Press: New York, 1978.
Knuth, D. Fundamental Algorithms
(The Art of Computer Programming, Volume 1,) Addison Wesley, 1968.
Lakatos, I.
Proofs and Refutations.
Cambridge University Press: Cambridge, 1976.
Lenat, D. B. Beings: knowledge as interacting experts.
Proc. of the 4th Int. Joint Conf. on Artificial Intelligence,
Tbilisi, USSR, 1975, 126-133.
Lenat, D. B. AM: an artificial intelligence approach to discovery in
mathematics as heuristic search. Memo AIM-286, Stanford AI Lab, 1976.
Lesser, V. R. and Erman, L. D. A retrospective view of the Hearsay-II
architecture.
Proc. of the 5th Int. Joint Conf. on Artificial Intelligence,
Cambridge, Mass., 1977, 790-800.
Low, J. Automatic coding: choice of data structures. Memo AIM-242,
Stanford University, 1974.
Lowerre, B. and Reddy, D. R. The Harpy system. In W. Lea (ed.),
Recent Trends in Speech Recognition.
Prentice-Hall: Englewood Cliffs, N. J., in press.
McCarthy, J. The advice taker. In M. Minsky (ed.),
Semantic Information Processing.
MIT Press: Cambridge, Mass., 1968.
Mostow, J. and Hayes-Roth, F. Machine-aided heuristic programming: a
paradigm for knowledge engineering. N-1007-NSF, The Rand Corporation,
Santa Monica, Calif., 1979 (in preparation).
Newell, A., Shaw, J. C., and Simon, H. A. Chess-playing programs
and the problem of complexity. In E. A. Feigenbaum and J. Feldman (eds.),
Computers and Thought.
McGraw-Hill: New York, 1963, 39-70.
Newell, A. and Simon, H.
Human Problem Solving.
Prentice-Hall: Englewood Cliffs, N.J., 1972.
Rips, L. J., Shobin, E. J., and Smith, E. E. Semantic distance and
the verification of semantic relations.
Journal of Verbal Learning and Verbal Be\-ha\-vi\-or, 12,
1973, 1-20.
Stefik, M. An examination of a frame-structured representation system.
Memo HPP-78-13, Stanford University, 1978.
Waterman, D. A., Anderson, R. H., Hayes-Roth, F., Klahr, P., Martins, G. R.,
and Rosenschein, S. Design of a rule-oriented system for implementing
expertise. The Rand Corporation, Santa Monica, 1979 (in preparation).
Waterman, D. A. and Hayes-Roth, F.
Pattern-Directed Inference Systems.
Academic Press: New York, 1978.
\NNSECP{Acknowledgements}
This research was supported in part by the National
Science Foundation under grants MCS76-nnnnn and MCS77-03273.
We also wish to thank John Seely Brown, Bruce Buchanan, Ed Feigenbaum,
Greg Harris, Barbara
Hayes-Roth, Allen Newell, Herbert Simon,
and Don Waterman for several discussions which have left their
mark in this paper.
\vfill\end